//
//  4.重建二叉树.swift
//  数据结构与算法
//
//  Created by ZERO on 2021/5/17.
//

import Foundation
/*
 题目：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
 思路：前序遍历序列中，第⼀个数字总是树的根结点的值。在中序遍历序列中，根结点的值在序列的中间，左⼦树的结点的值位于根结点的值的左边，⽽右⼦ 树的结点的值位于根结点的值的右边。剩下的我们可以递归来实现。
 */
func offer_4() {
    bfsOrder(Solution().reConstructBinaryTree([1, 2, 3, 4, 5, 6, 7], [3, 2, 4, 1, 6, 5, 7])!)
}

fileprivate class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param pre int整型一维数组
     * @param vin int整型一维数组
     * @return BinaryTreeNode类
     */
    func reConstructBinaryTree(_ pre: [Int], _ vin: [Int]) -> BinaryTreeNode<Int>? {
        // write code here
        return rebuild(pre: pre, preLeft: 0, preRight: pre.count - 1, vin: vin, vinLeft: 0, vinRight: vin.count - 1)
    }
    
    func rebuild(pre: [Int], preLeft: Int, preRight: Int, vin: [Int], vinLeft: Int, vinRight: Int) -> BinaryTreeNode<Int>? {
        if preLeft > preRight || vinLeft > vinRight { return nil }
        // 前序遍历的第一个一定是根节点
        let root = BinaryTreeNode<Int>(pre[preLeft])
        // 查找根节点在中序遍历数组中的位置
        var rootIndex = vinLeft
        while rootIndex <= vinRight && root.data != vin[rootIndex] {
            rootIndex += 1
        }
        root.leftNode = rebuild(pre: pre, preLeft: preLeft+1, preRight: preLeft+rootIndex-vinLeft, vin: vin, vinLeft: vinLeft, vinRight: rootIndex-1)
        root.rightNode = rebuild(pre: pre, preLeft: preLeft+rootIndex-vinLeft+1, preRight: preRight, vin: vin, vinLeft: rootIndex+1, vinRight: vinRight)
        return root
    }
}
